package 链表.两两交换链表中的节点;

import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/11/24 16:55
 * @description:两两交换链表中的节点，只能改变指针，不能改变值 没有头节点，第一个节点为首节点
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4))));
        ListNode listNode2 = new ListNode(null,new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(8))))));
     //   swapPairs2(listNode2);
        swapPairs3(listNode);
    }



    public static ListNode swapPairs3(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            //把temp.next指向temp.next.next
            temp.next = end;
            //头插法
            //TODO 这一行代码必不可少 表示将start以头插法的方式插入到end和end.next之间。
            start.next = end.next;
            end.next = start;
            //为下一轮循环做准备
            temp = start;
        }
        return pre.next;
    }

    //递归解法

    public ListNode swapPairs4(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode rest = head.next.next;
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = swapPairs4(rest);
        return newHead;
    }





}
